package demo.DataStrucAndAlgo.Sort;

import java.util.Arrays;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/8/3-08-03-20:39
 * @Description：demo.DataStrucAndAlgo.Sort   堆排序
 */
/*
堆排序
    通过顺序存储二叉树，将一个无序数组转变为一个完全二叉树
    第一阶段：创建堆（升序创建大顶堆（所有子树都满足父节点大于两个子节点），降序创建小顶堆（所有子树都满足父节点小于两个子节点））
    第二阶段：将根节点元素于树的最后一个元素对调位置（对调后最后一个元素成为最大值，将从树中脱离，不再参与操作）
    第三阶段：将剩余元素再次创建堆
 */
    /*
    排序过程：
        1、先以从右向左、从下向上的顺序，从最后一个非叶子结点开始，将其与其左右子节点进行比较，将大的与父节点位置对调
        2、重复以上操作，直到根节点的子树也被排完，形成大顶堆
        3、完成创建大顶堆后，将根节点元素与最后头的结点元素进行对调，对调完成后，最后的结点脱离树。
        4、将剩余的结点，从根节点开始，再次进行大顶堆的创建。不断调换、脱离，重建直到只剩根节点，排序完成
     */
public class heapSort {
    public static void main(String[] args) {
        int[] arr = {34,2,344,1,43,3,6,8,9,12,24};

        for (int i = arr.length-1; i >= 0; i--) {
            for ( int j = i/2; j >= 0; j--) {
                if( j*2+1 <= i && arr[j*2+1] > arr[j]){
                    change(arr,j,j*2+1);
                }
                if(j*2+2 <= i && arr[j*2+2] > arr[j]){
                    change(arr,j,j*2+2);
                }
            }
            change(arr,0,i);
        }
        System.out.println(Arrays.toString(arr));
    }
    public static void change(int[] arr, int i, int j){
        int temp;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
